/**
 * 哈希表
 */
;(function(window){
	/**
	 * 常用哈希算法
	 * 来源：http://blog.csdn.net/eaglex/article/details/6310727
	 * 按评分从高到低排列（https://www.byvoid.com/blog/string-hash-compare）
	 * @type {Object}
	 */
	var HashAlgorithm = {
		/**
		 * BKDR
		 * 这个算法来自Brian Kernighan 和 Dennis Ritchie的 The C Programming Language。这是一个很简单的哈希算法,使用了一系列奇怪的数字,形式如31,3131,31...31,看上去和DJB算法很相似。(这个就是Java的字符串哈希函数)
		 * @param str
		 * @return {Number}
		 * @constructor
		 */
		BKDRHash: function(str){
			var seed = 131; // 31 131 1313 13131 131313 etc..
			var hash = 0;
			var ln = str.length;
			for(var i = 0; i < ln; i++){
				hash = (hash * seed) + str.charCodeAt(i);
			}
			return hash;
		},
		/**
		 *
		 * @param str
		 * @return {Number}
		 * @constructor
		 */
		APHash: function(str){
			var hash = 0xAAAAAAAA;
			console.log(hash);
			for(var i = 0; i < str.length; i++){
				if ((i & 1) == 0)
					hash ^= ((hash << 7) ^ str.charCodeAt(i) * (hash >> 3));
				else
					hash ^= (~((hash << 11) + str.charCodeAt(i) ^ (hash >> 5)));
			}
			return hash;
		},
		/**
		 * DJB
		 * 这个算法是Daniel J.Bernstein 教授发明的，是目前公布的最有效的哈希函数。
		 * @param str
		 * @return {Number}
		 */
		DJBHash : function(str){
			var hash = 5381;
			for(var i = 0; i < str.length; i++){
				hash = ((hash << 5) + hash) + str.charCodeAt(i);
			}
			return hash;
		},
		/**
		 * JS
		 * Justin Sobel写的一个位操作的哈希函数。
		 * @param str
		 * @return {Number}
		 * @constructor
		 */
		JSHash: function(str){
			var hash = 1315423911;
			for(var i = 0; i < str.length; i++){
				hash ^= ((hash << 5) + str.charCodeAt(i) + (hash >> 2));
			}
			return hash;
		},
		/**
		 * RS
		 * 从Robert Sedgwicks的 Algorithms in C一书中得到了。我(原文作者)已经添加了一些简单的优化的算法，以加快其散列过程。
		 * @param str
		 * @return {Number}
		 * @constructor
		 */
		RSHash: function(str){
			var b = 378551;
			var a = 63689;
			var hash = 0;
			for(var i = 0; i < str.length; i++){
				hash = hash * a + str.charCodeAt(i);
				a = a * b;
			}
			return hash;
		},
		/**
		 * SDBM
		 * 这个算法在开源的SDBM中使用，似乎对很多不同类型的数据都能得到不错的分布。
		 * @param str
		 * @return {Number}
		 * @constructor
		 */
		SDBMHash: function(str)	{
			var hash = 0;
			for(var i = 0; i < str.length; i++){
				hash = str.charCodeAt(i) + (hash << 6) + (hash << 16) - hash;
			}
			return hash;
		},
		/**
		 * PJW
		 * 该散列算法是基于贝尔实验室的彼得J温伯格的的研究。在Compilers一书中（原则，技术和工具），建议采用这个算法的散列函数的哈希方法。
		 * @param str
		 * @return {Number}
		 * @constructor
		 */
		PJWHash: function(str)	{
			var BitsInUnsignedInt = 4 * 8;
			var ThreeQuarters = (BitsInUnsignedInt  * 3) / 4;
			var OneEighth = BitsInUnsignedInt / 8;
			var HighBits = (0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
			var hash = 0;
			var test = 0;
			for(var i = 0; i < str.length; i++){
				hash = (hash << OneEighth) + str.charCodeAt(i);
				if((test = hash & HighBits)  != 0){
					hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
				}
			}
			return hash;
		},
		/**
		 * ELF
		 * 和PJW很相似，在Unix系统中使用的较多。
		 * @param str
		 * @return {Number}
		 * @constructor
		 */
		ELFHash: function(str){
			var hash = 0;
			var x = 0;
			for(var i = 0; i < str.length; i++){
				hash = (hash << 4) + str.charCodeAt(i);
				if((x = hash & 0xF0000000) != 0){
					hash ^= (x >> 24);
				}
				hash &= ~x;
			}
			return hash;
		},
		/**
		 * DEK
		 * 由伟大的Knuth在《编程的艺术 第三卷》的第六章排序和搜索中给出。
		 * @param str
		 * @return {Number}
		 * @constructor
		 */
		DEKHash: function(str){
			var hash = str.length;
			for(var i = 0; i < str.length; i++){
				hash = ((hash << 5) ^ (hash >> 27)) ^ str.charCodeAt(i);
			}
			return hash;
		}
};

	/**
	 * 哈希表项对象
	 * @param hashKey
	 * @param data
	 * @return {Object}
	 * @constructor
	 */
	var DataItem = function(hashKey, data){
		return {
			key: hashKey,
			data: data
		};
	};

	/**
	 * 哈希表
	 * 选用BKDRHash方法作为字符串哈希算法
	 * @constructor
	 */
	var HashTable = function(){
		var size = 10;
		this._REHASH_CONST = 5;
		if( size < 5 ) throw new Error('哈希表大小不应小于'+this._REHASH_CONST);
		this._hashArr = new Array(size);
		this._maxSize = size;
		this._nil = DataItem(-1, null); // 空指针
		this._length = 0; // 哈希表的实际长度
	};
	HashTable.prototype = {
		constructor: HashTable,
		/**
		 * 首次对步长进行哈希
		 * @param key
		 * @return {Number}
		 */
		_stepHash: function(key){
			return key % this._maxSize;
		},
		/**
		 * 对步长二次哈希
		 * 其结果不能为0，并且数组长度最好是素数
		 * @param key
		 * @return {Number}
		 * @private
		 */
		_stepReHash: function(key){
			return this._REHASH_CONST - this._REHASH_CONST % 5;
		},
		/**
		 * 扩容数组
		 * 扩容为原数组长度的两倍
		 * @private
		 */
		_resize: function(){
			this._maxSize = this._maxSize*2;
			this._hashArr.length = this._maxSize;
		},
		/**
		 * 插入项
		 * @param key
		 * @param data
		 */
		insert: function(key, data){
			var hashVal = this._stepHash(HashAlgorithm.BKDRHash(key));
			var step = this._stepReHash(hashVal);
			while(this._hashArr[hashVal] != undefined && this._hashArr[hashVal].key != -1){
				// 遇到重复的key则覆盖
				if(this._hashArr[hashVal].key == key){
					this._hashArr[hashVal].data = data;
					break;
				}
				hashVal += step;
				hashVal %= this._maxSize;
			}
			this._hashArr[hashVal] = DataItem(key, data);
			this._length ++;
			// 检测并扩容数组
			if( this._maxSize - this._length < 10 ) this._resize();
		},
		/**
		 * 删除项
		 * @param key
		 * @return {*}
		 */
		deleteItem: function(key){
			var hashVal = this._stepHash(HashAlgorithm.BKDRHash(key));
			var step = this._stepReHash(hashVal);
			while(this._hashArr[hashVal] != undefined){
				if(this._hashArr[hashVal].key == key){
					var tmp = this._hashArr[hashVal];
					this._hashArr[hashVal] = this._nil;
					this._length --;
					return tmp.data;
				}
				hashVal += step;
				hashVal %= this._maxSize;
			}
			return null;
		},
		/**
		 * 获取项
		 * @param key
		 * @return {*}
		 */
		getItem: function(key){
			var hashVal = this._stepHash(HashAlgorithm.BKDRHash(key));
			var step = this._stepReHash(hashVal);
			while(this._hashArr[hashVal] != undefined){
				if(this._hashArr[hashVal].key == key){
					return this._hashArr[hashVal].data;
				}
				hashVal += step;
				hashVal %= this._maxSize;
			}
			return null;
		}
	};

	window.HashTable = HashTable;
	window.HashAlgorithm = HashAlgorithm;
})(window);